package q134_canCompleteCircuit;

public class Solution_2 {

    /**
     * 利用图的思想来解决问题，我们从起点开始画一张剩余油量的折线图，可以发现图中有在0上面的也有在0下面的点
     * 那么在0下方的值最小的点开始，就是最缺少油的位置，从这个点的后一个点开始如果还是不能够成功开完全程，就意味着无法成功
     *
     * 答主的思路，答主这个图是从0点（i=0,即第一个站）出发的折线图，那么改变出发点时，这个图会怎么变化呢？
     * 你可以自己去画一画，你会发现，整体折线图的形状是没有变的，改变的是y值，相当于将折线图在Y轴方向上上下平移。
     * 那么，当最小点落在X轴上时（也就是使得最小点y=0时），整体折线在X轴上方，y值恒大于等于0，也就是剩余油量一直不为负，可以绕行一圈。
     * 对于本例，也就是使得i=3时，y=0。
     * 此时，意味着从i=3，第四个站出发，到此站时即没有加油也没有耗油，剩余油量为0。
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int leftGas = 0, start = 0;
        int minGas = Integer.MAX_VALUE;
        for (int i = 0; i < gas.length; i++) {
            leftGas += gas[i] - cost[i];
            if(leftGas < minGas){
                minGas = leftGas;
                start = i;
            }

        }
        return leftGas < 0 ? -1 : (start + 1) % gas.length;
    }




}
